package org.sanguine.study.hometasks.second;

import java.util.Arrays;
import java.util.Comparator;
import java.util.NavigableSet;
import java.util.PriorityQueue;
import java.util.TreeSet;

public class Races {
	private Double[] speedOfCars;
	private PriorityQueue<Object[]> data;
	
	/**
	 * Start new race with n racers
	 * @param n (must be greater than zero)
	 * @throws IllegalArgumentException if n is negative or zero
	 */
	
	public Races(int n) {
		if (n <= 0) throw new IllegalArgumentException("Number of cars must be greater than zero");
		
		speedOfCars = new Double[n];
		data = new PriorityQueue<>(n, new Comparator<Object[]>() {

			@Override
			public int compare(Object[] o1, Object[] o2) {
				int result = ((Double)o2[0]).compareTo((Double)o1[0]);
				
				return (result == 0) ? ((Integer)o1[1]).compareTo((Integer)o2[1]) : result;
			}
		});
	}
	
	/**
	 * Set speed for all cars.  [0] - first position from start, [N - 1] - last position from start
	 * @param array of speeds(double) according to position.  Negative speed is not allowed.
	 * @throws IllegalArgumentException if speeds arguments is not set properly.  
	 */
	
	public void setSpeed(Double[] speeds) {
		if (speeds == null
			|| speeds.length != speedOfCars.length) throw new IllegalArgumentException("Speed of cars must be set properly");
		
		for (Double sp : speeds)
			if (sp == null || sp < 0.0) throw new IllegalArgumentException("Negative or Null speed is not allowed");
		
		speedOfCars = Arrays.copyOf(speeds, speeds.length);
	}

/*	public int getNumberOfOvertaking() { // O(n^2)
		int count = 0;
		for (int pos = speedOfCars.length - 1; pos >= 1; pos--)
			for (int prevPos = pos - 1; prevPos >= 0; prevPos--)
				if (speedOfCars[pos] > speedOfCars[prevPos]) count++;
		return count;
	}
*/

	/**
	 * Get number of overtaking during the race
	 * @return number of overtaking
	 */
	
	public int getNumberOfOvertaking() { // O(n log n)
		data.clear();
		for (int i = 0; i < speedOfCars.length; i++) data.add(new Object[]{new Double(speedOfCars[i]), new Integer(i)});
		
		NavigableSet<Integer> countedPositions = new TreeSet<>();

		int count = 0;
		while (!data.isEmpty()) {
			Integer fastestPosition = (Integer)data.poll()[1]; //get position of the current fastest car
			count += fastestPosition;
			int correction = countedPositions.headSet(fastestPosition).size();
			count = count - correction;
			countedPositions.add(fastestPosition);
		}
		return count;
	}

}
